package com.platform.modules.alg.alglib.hdu2222;

import java.util.LinkedList;
import java.util.Queue;

public class Hdu2222 {

    public static int K = 26;

    public String output = "";

    void init() // 初始化
    {
        superRoot = new node();
        root = new node();
        root.fail = superRoot;
        for (int i = 0; i < K; i++)
            superRoot.ch[i] = root;
        superRoot.count = -1;
    }

    private node superRoot;
    private node root;

    void insert(String str) // Trie 的插入
    {
        node t = root;
        int len = str.length();
        for (int i = 0; i < len; i++) {
            int x = str.charAt(i) - 'a';
            if (t.ch[x] == null)
                t.ch[x] = new node();
            t = t.ch[x];
        }
        t.count++;
    }

    void build_ac() {
        Queue<node> q = new LinkedList<>(); // 队列，BFS使用
        q.add(root);
        while (!q.isEmpty()) {
            node t;
            t = q.peek();
            q.poll();
            for (int i = 0; i < K; i++) {
                if (t.ch[i] != null) {
                    t.ch[i].fail = t.fail.ch[i];
                    q.add(t.ch[i]);
                } else
                    t.ch[i] = t.fail.ch[i];
            }
        }
    }

    int query(String str) {
        int ans = 0;
        node t = root;
        int len = str.length();
        for (int i = 0; i < len; i++) {
            int x = str.charAt(i) - 'a';
            t = t.ch[x];
            for (node u = t; u.count != -1; u = u.fail) {
                ans += u.count;
                u.count = -1;
            }
        }
        return ans;
    }

    public String cal(String input) {
        int n;
        String str1;
        String str2;
        init();
        String[] line = input.split("\n");
        n = Integer.parseInt(line[0]);
        int count = 1;
        while (n-- > 0) {
            str2 = line[count++];
            insert(str2);
        }
        build_ac();
        str1 = line[count];
        output += query(str1) + "\n";
        return output;
    }
}

class node {
    node fail;
    node ch[] = new node[Hdu2222.K];
    int count;

    node() {
        fail = null;
        for (int i = 0; i < ch.length; i++) {
            ch[i] = null;
        }
        count = 0;
    }
}
